/*有向图的连通分量 

* 1.有向无环图(拓扑图)可以用来求:是否存在一个点使得其他所有点都能到达这个点，并算出这个点有多少个,
    步骤:
    将每个点的出度数求出。
    如果出度为0的点数只有一个，说明存在这样的点，数量即为这个点所在的连通块的点数。
    如果出度为0的点数不止一个，说明一定存在某个点到不了另外一个点。说明不存在这样的点。

* 2.有向无环图可以用来求:问将某个东西供给给哪些点，最后这些东西可以遍布整个图。
    步骤:
    将图变成有向无环图。
    求这个有向无环图每个点的入度数。
    入度为0则说明为这张图的起点，起点的个数即为需要供给东西的点，这样从这些点开始，便会遍历整张图。

* 3.有向无环图可以用来求:问最少加多少条边，可以使得这个图变成强连通图。
    步骤:
    将图变成有向无环图。
    算出这个图入度为0的点的数量in cnt和出度为0的点的数量out cnt，变成强连通图
    即需要添加max(in cnt，out cnt)

* 4.Tarjan算法：
    目标：求强连通分量，最后可以得到每个结点所属的连通块。
    用到的结构：
        （1）dfn[i]：存结点i第一次被访问的编号(时间戳)。
        （2）low[i]：存从结点i出发，能访问到的所有结点里时间戳最早的结点。
        （3）timestamp：给时间戳赋值的变量。
        （4）stk[]：表示栈空间。
        （5）in_stk[i]：表示结点i是否在栈里。
        （6）top：表示指向栈顶的变量。
        （7）id[i]：表示结点i所属的连通块是哪一个。
        （8）scc_cnt：表示连通块的数量/编号。 //  Strongly Connected Components 强连通分量
        （9）Size[i]：表示第i个连通块的大小。

* 本题:
    N 颗恒星的亮度值总和至少有多大
    求最小 -> 求所有下界的最大 -> 最长路 √
    求最大 -> 求所有上界的最小 -> 最短路

    最长路: dist[j] >= dist[t] + w[i]  t+w[i]->j

    T=1: A=B  -> A>=B B>=A   B+0->A A+0->B
    T=2: A<B  -> B>=A+1     A+1->B
    T=3: A>=B -> A>=B       B+0->A
    T=4: A>B  -> A>=B+1     B+1->A
    T=5: A<=B -> B>=A       A+0->B

    spfa最长路 - 做完后每个点的距离就是最小值
    (1) 边是正的 - 存在正环 -> 无解
    (2) 有解: 1.必须有绝对值 2.超级源点(能到所有边) 3.x[i]>=x[0]+1
*/

#pragma GCC optimize("O1,O2,O3,Ofast")
#pragma GCC optimize("no-stack-protector,unroll-loops,fast-math,inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,sse4,sse4.1,sse4.2,ssse3")

#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_set>
#include<stack>
// #define ONLINE_GUDGE
using namespace std;
using LL = long long;
const int N = 100010, M = 600010, INF = 0x3f3f3f3f;

int n, m;
int h[N], hs[N], e[M], ne[M], w[M], idx;
int dfn[N], low[N], timestamp; // dfs序 最小访问时间 时间戳
// int stk[N], top; // 栈 栈顶指针
stack<int> stk; // 内置DS优化
bool in_stk[N]; // 判断结点是否在栈中
int id[N], scc_cnt, sze[N]; // id数组存储每个点所在的连通分量编号 sze数组统计每个连通分量的点的数量
int dist[N];

void AddEdge(int h[], int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;//  
}

void Tarjan(int u){
    dfn[u] = low[u] = timestamp++ ;
    // stk[ ++ top ] = u, in_stk[u] = true;
     
    stk.push(u); 
    in_stk[u] = true;

    for(int i = h[u]; ~i; i = ne[i]){
        int v = e[i];
        if(!dfn[v]){
            Tarjan(v);
            low[u] = min(low[u], low[v]); // 用u的邻点j更新u所能到达的结点最小时间戳
        }else if(in_stk[v]) low[u] = min(low[u], dfn[v]);
    }

    if(dfn[u] == low[u]){ // u是最靠上的节点
        ++ scc_cnt; // 连通分量 + 1
        int y;
        do{
            // y = stk[ top -- ];
            y = stk.top(); stk.pop();
            in_stk[y] = false;
            id[y] = scc_cnt;
            sze[scc_cnt] ++;
        }while(y != u);
    }
}

int main()
{

    #ifdef ONLINE_JUDGE

    #else
    freopen("./in.txt","r",stdin);
    #endif
    ios::sync_with_stdio(false);   
	cin.tie(0);
    
    cin >> n >> m;
    memset(h, -1, sizeof h);
    memset(hs, -1, sizeof hs);

    // 超级源点
    for(int i = 1; i<=n; i++) AddEdge(h, 0, i, 1);

    for (int i = 1; i <= m; i ++ )
    {
        int t, a, b; cin >> t >> a >> b;
        if(t==1) AddEdge(h, b, a, 0), AddEdge(h, a, b, 0);
        else if(t==2) AddEdge(h, a, b, 1);
        else if(t==3) AddEdge(h, b, a, 0);
        else if(t==4) AddEdge(h, b, a, 1);
        else AddEdge(h, a, b, 0);
    }

    Tarjan(0);

    bool success = true;
    for(int u = 0; u <= n; u++){
        for(int i = h[u]; ~i; i = ne[i]){
            int v = e[i];
            int a = id[u], b = id[v]; // a b 表示两个连通分量的编号
            if(a == b)
            {    
                if(w[i] > 0)
                {
                    success = false;
                    break;
                }
            }
            else AddEdge(hs, a, b, w[i]); // 不在同一scc中, 加边
            // cerr << "a: " << a << " b: " << b << " i: " << i << " w[i]: " << w[i] << " idx: " << idx << endl; 

        }

        if(!success) break;
    }

    if(!success) cout << "-1" << endl;
    else{
        for(int u = scc_cnt; u; u--){
            for(int j = hs[u]; ~j; j = ne[j]){
                int v = e[j];
                dist[v] = max(dist[v], dist[u] + w[j]);
                // cerr << "u: " << u << " j: " << j << " v: " << v << " dist[v]: " << dist[v] << endl;

            }
        }

        
        LL res = 0;
        for(int i = 1; i <= scc_cnt; i++)
            res += 1ll * dist[i] * sze[i]; 
            // 结果 = 新图里每个scc的距离 * scc里的点数 = dist[scc] * cnt[scc] 

        cout << res << endl;
    }    
    
    return 0;
}

